{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Markov Chain\n",
    "## Introduction\n",
    "Markov chains are stochastic processes in which the state of the system alters between a given set of possible states (i.e. a state machine),\n",
    "according to a set of transition probabilities between states. This concept is illustrated in the following image:\n",
    "\n",
    "![Markov Chains](img/Markov_chains.png){width=50%}\n",
    "\n",
    "Note that the transition probabilities do not depend on previous states. This\n",
    "*memorylessness* characteristic is known as a **Markov property** and is the most outstanding characteristic of Markov Chains.\n",
    "\n",
    "Markov chains allow to analyse the performance of a system and compare various alternatives to support decision making.\n",
    "\n",
    "## Set up\n",
    "A Markov Chain is a sequence of stochastic variables: \n",
    "\n",
    "${𝑋}=𝑋_1,𝑋_2,𝑋_3, …,𝑋_t$\n",
    "\n",
    "That represent the sequence of states of a system in a sequence of discrete time events ($t \\in [0,1,...,T]$). At any given instance of time, the system can only be in one of the possible n states ${S}=[S_1, S_2, ..., S_n]$), that is: \n",
    "\n",
    "$X_t \\in  [S_1, S_2, ..., S_n] \\quad \\forall t \\in [1, 2, ..., T]$\n",
    "\n",
    "As in the figure above, an n-state Markov system is characterised by a nxn transition probability matrix which contains the different transition probabilities. For instance, the 3-state system in the image above is a system with 3 possible states ${𝑆}=[𝑆_1,𝑆_2,𝑆_3]$. The 3-state system is characterised by the matrix:\n",
    "\n",
    "$P^{(1)}=\\begin{bmatrix}\n",
    "p_{11} & p_{12} & p_{13}\\\\\n",
    "p_{21} & p_{22} & p_{23}\\\\\n",
    "p_{31} & p_{32} & p_{33}\n",
    "\\end{bmatrix}$\n",
    "\n",
    "where $p_{ij}$ is the probability that the system is in state $j$ in the next instant of time, given that the system is in state $i$:\n",
    "\n",
    "$p_{ij} = P(X_{t+1} = S_j | X_{t} = S_i) \\quad \\forall t \\in [1, 2, ..., T]$\n",
    "\n",
    "In other words, the probability that the system is in state $j$ in instant $t + 1$ only\n",
    "depends on the state $i$ in which the system was in the previous instant $t$, and does not\n",
    "depend on the states in which it was before. This probability is known as a **one-step\n",
    "transition** and consequently, the matrix $P^{(1)}$ is known as the one-step probability matrix. The markov property states that this probability does not change with time, that it can be considered\n",
    "stationary. This is the main modeling assumption made when using Markov chains to model the behavior of a system.\n",
    "\n",
    "Let us now vector $𝑉_𝑡$ represent the probability of being at any given state. Then, the probabilities in t+1 can be estimated as:\n",
    "\n",
    "$V_{t+1} = V_t*P^{(1)}$\n",
    "\n",
    "For instance, in the example above, let us assume that the system is in state 1 at instant $t$: \n",
    "\n",
    "$V_t = [1 \\quad 0 \\quad 0]$\n",
    "\n",
    "The probabilities of the system at state $t+1$ are: \n",
    "\n",
    "$V_{t+1} = V_t*P^{(1)} = [p_{11} \\quad p_{12} \\quad p_{13}]$\n",
    "\n",
    "Similarly, the probabilities of the system after $k$ steps is: \n",
    "\n",
    "$V_{t+1} = V_t*P^{(k)} = V_t*\\left(P^{(1)}\\right)^k$\n",
    "\n",
    "When k is large enough, the transition probabilities stabilise and the probability that a system is in any given state do not depend on the initial state. These probabilities are called stationary probabilities and are calculated using the following system of equations:\n",
    "\n",
    "$\\pi_j = \\sum_{i=1}^{n}\\pi_i*p_{ij} \\quad \\forall j$\n",
    "\n",
    "$\\sum_{j=1}^{n}\\pi_j = 1$\n",
    "\n",
    "where $\\pi_j$ is the stationary probability that the system is in state $j$. \n",
    "\n",
    "Stationary probabilities represent the long term behavior of the system, and can be used to gain insights on the system behaviour. \n",
    "\n",
    "For instance, if there is a cost $c_j$ associated to the system state $j$, the **long term average cost** $C$ can be calculated as:\n",
    "\n",
    " $C = \\sum_{j=1}^{n}c_j*\\pi_j$\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}